In the early days of computers, memories were expensive and small. Early programmers spent large amounts of time trying to squeeze programs into tiny memory, and often were forced to divide programs into pieces called "overlays" each of which could fit in memory at one time. As software technologies improved, a technique known as "virtual memory" was developed, wherein the concepts of address space and actual physical memory locations were separated. As known to those skilled in the art, the number of addressable words accessible by a computer depends on the number of bits in the address field and is in no way related to the number of memory words actually available. For example, a hypothetical computer having a sixteen-bit address field can theoretically address 65,536 (64K) words of memory. However, if only 4096 (4K) words of main memory are provided, the addressing capability of the computer is not being fully exploited. As used herein, the term "address space" represents the number of words a particular computer can address utilizing all bits of the address field provided in the computer architecture. In the hypothetical computer referenced above, the address space comprises the numbers 0, 1, 2, . . . 65,535, the set of possible addresses.
In a classical virtual memory, there is provided a fixed number of actual, physical words of memory. The address space of the computer is "mapped" onto the physical memory, by translating addresses in the address space into physical memory locations. For example, in the hypothetical machine referenced above having 4K words of memory, a "map" may be created for containing information which relates addresses generated in the 64K address space of the computer to addresses in the 4K main memory. For purposes of the present application, the addresses that a computer program can refer to, a function of the computer architecture, shall be referred to as the "virtual address space" and the actual, hard-wired memory addresses are defined as the "physical address space". A "memory map" relates virtual addresses to physical addresses. Accordingly, it will be understood that programs may load from, or store into, any word in the virtual address space, or jump to any instruction within the virtual address space, without regard to whether there is any actual data at those virtual addresses.
Most conventional virtual memory systems determine when a portion of memory (known typically as a "page" or "segment") not physically present in the main memory has been addressed by the computer, locate the desired information in a secondary memory such as a bulk storage device, load the information from the secondary memory into the main memory, and modify the memory map to reflect that the virtual address provided by the computer now relates to a specific particular physical address in the main memory which contains the located and now-loaded desired information. In this regard, reference is made to the classical article on virtual memory, Denning, "Virtual Memory", Computing Surveys, Vol. 2, pp 153-189 (September, 1970), reproduced in Freeman, "Software Systems Principles--A Survey", Science Research Associates, Inc., pp. 204-257 (1975), which is incorporated herein by reference and made a part hereof, and will not be discussed further herein.
One problem frequently encountered in conventional virtual memory systems is the need to relocate information retrieved from a secondary memory source such as a disk drive or the like, prior to making the information available for accessing through the memory map. For example, most conventional virtual memory systems employ a disk drive or other mass storage media as a secondary memory for storing programs and data which are not presently being accessed by the operating program. When the virtual memory system determines that a segment or page of information from the secondary memory is required, the computer operating system or special purpose hardware commands the disk drive to deliver the desired information. The data transferred from the secondary memory may be loaded by a direct memory access (DMA) mechanism, or may be loaded on demand under control of the central processing unit (CPU).
Recently, there has been a trend toward providing distributed computing and data storage capabilities, so that a plurality of satellite processors can share a remotely-located disk drive or other peripheral resource via a communications network. For example, many personal computer networks are designed to include a disk drive as secondary memory which can simultaneously serve a plurality of central processing units. The various satellite or remote CPU's share access to the disk drive on a time-sharing basis when programs or data are to be loaded. A "network server" allocates use of the system resources between processors connected to the network. In order to serve a plurality of CPU's, it is necessary for the network server to maintain records as to the source and usage of blocks of data, so that if modifications or updates have been made to a block of data, the server can find the original stored block for updating.
Blocks of data transferred via a communications network are frequently referred to as "pages", "segments", "packets", and the like. These terms are also frequently used in connection with virtual memory systems. In many communication networks, a page or other transferred block comprises a header, a data portion, and a trailer. Typically, information such as the address of a page or segment of data in a secondary memory are stored in the header portion, which precedes the actual useful data. The trailer which follows the data usually is present for determining data accuracy through cyclic redundancy checking (CRC) or other data integrity scheme.
In some computer systems, a portion of memory is reserved for receiving DMA transfers of blocks of data from peripherals, including network transfers. Once a page of information has been loaded by the DMA to this reserved area, it may be necessary to retransfer the desired information without the associated header and trailer to another portion of memory which has been mapped for use in connection with implementing virtual memory. This necessitates a separate data transfer from the reserved memory area to the mapped virtual memory area. It will accordingly be understood that additional processor and/or system resources must be devoted to retransferring the information from the reserved DMA transfer or "holding" area to the virtual memory area. Needless to say, such usage of system resources to first transfer a desired page into a DMA holding area, and then to retransfer only the desired portion of a retrieved page to the virtual memory area, with header and trailer portions stripped, is time consuming and wasteful. Accordingly, there is a need for a virtual memory system for operation with communication network systems, which does not require the relocation of the desired information once a DMA transfer has been made. Prior to the present invention, it has not been possible to construct a virtual memory system, even employing DMA techniques, without requiring transfers of data from a DMA holding area to a virtual memory mapped area.
Other problems exist in virtual memory systems management. In many prior art virtual memory systems, means are provided for detecting the occurrence of a "page fault" condition. A "page fault" condition occurs when a virtual memory CPU attempts to address a portion of the virtual address space which corresponds to data or programs not currently resident in the primary memory, necessitating a data transfer from secondary memory prior to successful completion of the instruction which generated the page fault. Page fault detecting means typically interrupt execution of the instruction which generated the page fault, resulting in the presence of invalid or erroneous data in the data registers of the computer. In another approach, the computer is allowed to complete the execution of the instruction which generated the page fault and any subsequent instructions dependent thereupon, a technique which also results in the creation of erroneous data in the data registers of the computer.
Each of the foregoing prior art techniques for operation subsequent to correction of a page fault requires either the reexecution of the instruction or sequence of instructions which generated the page fault so as to correct the information contained in the data registers, or the provision of special circuitry or other means for correcting the results of the execution of the instruction, again to correct the information in the data registers. All of the foregoing prior art techniques may slow down system operation because instructions must be reexecuted or other corrective instructions must be executed to correct erroneous data values. Thus, there is a need for a virtual memory system which does not require interruption or reexecution of instructions by the central processing unit in the event of a page fault condition.
Finally, there have been problems in obtaining measurements useful in memory allocation and management in prior art virtual memory systems. Many prior art systems employ a memory map which includes table entries for memory management purposes. These table entries typically include extra bits for measuring and/or labelling segments of information. These extra bits typically include a "modified" bit, which is set if a page was modified by processing since being placed in memory; a "used" bit, which is set whenever a page is referenced so that a metering routine can compile statistics on page use; and an "unused" bit which signifies that a page in memory has not been referenced by a program that demanded it, and therefore should not be removed until it has been used. The "used" bits are useful for determining a working set as described in the referenced Denning article. In most prior art virtual memory systems, these extra or "housekeeping" bits are maintained as map entries associated with the address translations which reference the virtual address space to the physical address space. However, in order to use the information contained in the housekeeping bits, it is necessary for the operating system or other program to access the housekeeping information either periodically or on a time multiplexed basis, so as to optimize the usage of the virtual memory. This requires processor overhead time and necessarily delays execution of desired applications programs. Accordingly, there is a need for a virtual memory management system which does not require dedication of main processor resources for performing virtual memory management and optimization.